package com.jia.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Pro0018 {


	/**
	 * //加了三个判断条件
	 * 执行用时：
	 * 4 ms
	 * , 在所有 Java 提交中击败了
	 * 92.36%
	 * 的用户
	 * 内存消耗：
	 * 40.1 MB
	 * , 在所有 Java 提交中击败了
	 * 10.53%
	 * 的用户
	 * @param nums
	 * @param target
	 * @return
	 */
	public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		Arrays.sort(nums);
		int len = nums.length;
		for(int i = 0; i + 3 < nums.length; i++) {
			if(i > 0 && nums[i-1] == nums[i]) continue; //去重
			//判断条件
			//判断条件
			if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) return result;
			if(nums[len-1] + nums[len - 2] + nums[len - 3] + nums[i] < target) continue;
			for(int j = i + 1; j + 2 < nums.length; j++) {
				if(j > i+1 && nums[j-1] == nums[j]) continue;//去重
				//判断条件
				if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
				int l = j + 1, r = nums.length - 1;
				while(l < r) {
					if(nums[i] + nums[j] + nums[l] + nums[r] == target) {
						result.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
						while(l < r && nums[l+1] == nums[l]) ++l;
						while(l < r && nums[r-1] == nums[r]) --r;
						++l;
						--r;
					}else if(nums[i] + nums[j] + nums[l] + nums[r] > target) {
						--r;
					}else {
						++l;
					}
				}
			}
		}
		return result;
	}
    public List<List<Integer>> fourSum2(int[] nums, int target) {
    	List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i =0; i <nums.length-3; i++) {
        	if(i>0 && nums[i] == nums[i-1]) continue;
        	for(int j = i+1; j < nums.length -2; j++ ) {
        		if(j>i+1 && nums[j] == nums[j-1]) continue;
        		int low = j + 1, hight = nums.length-1, sum = target - nums[i] - nums[j];
        		while(low < hight) {
        			if(nums[low] + nums[hight] == sum) {
        				res.add(Arrays.asList(nums[i], nums[j], nums[low], nums[hight]));
        				while(low<hight && nums[low] == nums[low+1]) ++low;  //去重
            			while(low < hight && nums[hight] == nums[hight-1]) --hight;//去重
        				++low;
        				--hight;
        			}else if(nums[low] + nums[hight] > sum) {
        				--hight;
        			}else {
        				++low;
        			}
        		}
        	}
        }
        return res;
    }
    public static void main(String[] args) {
		Pro0018 pro0018 = new Pro0018();
//		int[] nums = {1, 0, -1, 0, -2, 2};
//		int[] nums = {-3,-2,-1,0,0,1,2,3};
//		int[] nums = {0, 0, 0, 0};
		int[] nums = {-1,0,-5,-2,-2,-4,0,1,-2};
		int target = -9;
		System.out.println(pro0018.fourSum(nums, target));
	}
}
